/**
 * Created with IntelliJ IDEA.
 * Description:建大堆&堆排序
 * User: dings
 * Date: 2024-08-17
 * Time: 13:18
 */

//建大堆
public class Heap {
    public void createHeap(int[] arr) {
        int parent = (arr.length-1-1)/2;
        while (parent >= 0) {
            siftDown(arr,parent,arr.length);
            parent--;
        }
    }

    /**
     * 向下调整算法
     * @param arr
     * @param parent
     */
    private void siftDown(int[] arr, int parent,int usedSize) {
        int child = parent*2+1;
        while (child < usedSize) {
            if (child+1 < usedSize) {
                if (arr[child+1] > arr[child]) {
                    child += 1;
                }
            }
            if (arr[child] > arr[parent]) {
                swap(arr,parent,child);
            }else {
                break;
            }
            parent = child;
            child = parent*2+1;
        }
    }

    /**
     * 向上调整算法
     * @param arr
     * @param i
     * @param j
     */

    private void siftUp(int[] arr,int childIndex) {
        int parent = (childIndex-1)/2;
        while (parent >= 0) {
            if (arr[childIndex] > parent) {
                swap(arr,parent,childIndex);
                childIndex = parent;
                parent = (childIndex-1)/2;
            }else {
                break;
            }
        }
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /**
     * 堆排序
     * @param arr
     */
    public void heapSort(int[] arr) {
        int end = arr.length-1;
        while (end > 0) {
            swap(arr,0,end);
            siftDown(arr,0,end);
            end--;
        }
    }
}
